package com.lw.leetcode.node;

import com.lw.leetcode.node.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 113. 路径总和 II
 * 437. 路径总和 III
 * 面试题 04.12. 求和路径
 *
 * @Author liw
 * @Date 2021/4/29 11:07
 * @Version 1.0
 */
public class PathSum {

    public List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
        List<List<Integer>> all = new ArrayList<>();
        if (root == null) {
            return all;
        }
        List<Integer> list = new ArrayList<>();
        find2(root, targetSum, all, list, 0);
        return all;
    }

    public void find2(TreeNode root, int targetSum, List<List<Integer>> all, List<Integer> list, int sum) {
        int value = root.val + sum;
        if (root.left == null && root.right == null) {
            if (value == targetSum) {

                List<Integer> li = new ArrayList<>(list);
                li.add(root.val);
                all.add(li);
            }
            return;
        }
        int size = list.size();
        list.add(root.val);
        if (root.left != null) {
            find2(root.left, targetSum, all, list, value);
        }
        if (root.right != null) {
            find2(root.right, targetSum, all, list, value);
        }
        list.remove(size);
    }


    int count = 0;

    public int pathSum3(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        find3(root, targetSum, list);
        return count;
    }

    public void find3(TreeNode root, int targetSum, List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        int size = list.size() - 1;
        int sum = 0;
        for (int i = size; i >= 0; i--) {
            sum += list.get(i);
            if (sum == targetSum) {
                count++;
            }
        }
        find3(root.left, targetSum, list);
        find3(root.right, targetSum, list);
        list.remove(size);
    }

}
